COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	balance[f81,jmc]		Balanced trees instead of a-lists
C00006 ENDMK
C⊗;
;;;balance[f81,jmc]		Balanced trees instead of a-lists

(defun contents (x u)
       (cond ((null u) (fail))
	     ((eq x (car u)) (cadr u))
	     ((lessp x (car u)) (contents x (car (cddddr u))))
	     (t (contents x (caddr (cddddr u))))))

;;;structure of tree::= nil | (x val) | (x val nl l nr r)
;;; The following definition uses LISP 3 notation wherein
;;; 1 = car
;;; 2 = cadr
;;; 3 = caddr
;;; etc.
;;; 0 = λx.x
;;; -1 = cdr
;;; -2 = cddr
;;; -3 = cdddr
;;; etc.

c(x,u) ← if null u then fail[]
	else if x = 1 u then 2 u
	else if x < 1 u then c(x, 4 u)

count z ← if null -2 z then 0[SOMETHING MISSING] else 3 z + 5 z
	else c(x,6 u)

a(x,val,u) ←	if null u then <x, val>
		else if x = 1 u then [if val = 2 u then u else <x,val.-2 u>]
		else if null -2 u then [if x < 1 u then <1 u,2 u,1,<x,val>,0,nil>
					else <1 u,2 u, 0,nil, 1, <x,val>>]
		else if x < 1 u then
			[if 3 u ≤ 5 u then {a(x,val,4 u}[λz.<1 u,2 u,count z,z,-4 u]]
		else if 5 u ≤ 3 u then {a(x,val,6 u}[λz.<1 u,2 u,3 u,4 u,count z,z>]
		else {a(1 u, 2 u, 6 u)}[λz.<x,val,3 u,4 u,count z,z>]

(defun assign (x val u)
       (cond ((null u) (list x val))
	     ((eq x (car u)) (cond ((equal val (cadr u)) u)
				   (t (cons x (cons val (cddr u))))))
	     ((null (cddr u)) (cond ((lessp x (car u)) (list (car u)
							      (cadr u)
							      1
							      (list x val)
							      0
							      nil))
				    (t (list (car u)
					     (cadr u)
					     0
					     nil
					     1
					     (list x val)))))
	     ((lessp x 1) (cond ((lessp (cadddr u) (cadr (caddddr u)))
				 ((lambda (z) (rcons (car u)
						     (cadr u)
						     (count z)
						     z
						     (cddddr u)))
				  (assign x val (caddr (cddddr u)))))


		else if x < 1 u then
			[if 3 u ≤ 5 u then {a(x,val,4 u}[λz.<1 u,2 u,count z,z,-4 u]]
		else if 5 u ≤ 3 u then {a(x,val,6 u}[λz.<1 u,2 u,3 u,4 u,count z,z>]
		else {a(1 u, 2 u, 6 u)}[λz.<x,val,3 u,4 u,count z,z>]